package features.advance.leetcode.linkedlist.medium;

import features.advance.leetcode.Solution;
import features.advance.leetcode.geometry.doublepointer.easy.ListNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 *
 * 19. 删除链表的倒数第 N 个结点
 * 难度：中等
 *
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 *
 *
 * 提示：
 *
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 *
 *
 * @author LIN
 * @date 2021-04-30
 */
public class Solution19 extends Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode h = head;
        ListNode curr = head;
        ListNode prev = null;
        int i=0;
        Map<Integer,ListNode> map = new LinkedHashMap<>();
        while(curr!=null){
            map.put(i++,curr);
            System.out.println(curr.val);
            prev = curr;
            curr = curr.next;
        }
        int size = map.size();
        if(size <= 1){
            return null;
        }else if(n == size){
            return head.next;
        }
        map.get(size - n - 1).next = map.get(size - n).next;
        return head;
    }
    public static void main(String[] args) {
        String str = "[1,2,3,4,5]";
        int n = 2;
        ListNode listNode = TreeUtil.parseLinkedList(str);
        Solution19 solution19 = new Solution19() {
            @Override
            public ListNode removeNthFromEnd(ListNode head, int n) {
                ListNode dummy = new ListNode(0, head);
                ListNode first = head;
                ListNode second = dummy;
                for (int i = 0; i < n; ++i) {
                    first = first.next;
                }
                while (first != null) {
                    first = first.next;
                    second = second.next;
                }
                second.next = second.next.next;
                ListNode ans = dummy.next;
                return ans;
            }
        };
        ListNode listNode1 = solution19.removeNthFromEnd(listNode, n);
        System.out.println(listNode1);
    }
}
